package 剑指offer;

import java.util.ArrayList;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-01
 */
public class 括号生成 {
    /*给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
    例如，给出n=3，解集为：
            "((()))", "(()())", "(())()", "()()()", "()(())",*/
    public static void main(String[] args) {
        System.out.println(generateParenthesis(4));
        System.out.println(generateParenthesis1(4));

    }

    public static String LStr = "(";
    public static String RStr = ")";
    public static String ALL = "()()()()";

    /**
     * @param n int整型
     * @return string字符串ArrayList
     */
    public static ArrayList<String> generateParenthesis(int n) {
        // write code here
        ArrayList<String> result = new ArrayList<>();
         generateParenthesis(n, "", 0, 0, result);
        return result;
    }

    public static void generateParenthesis(int n, String append, int left, int right,  ArrayList<String> result) {
        // write code here


        if (left == n && right == n) {
            result.add(append);
        }
        //左括号一定在右括号前面
        if (append.equals("")) {
            generateParenthesis(n, append + "(", left + 1,right, result);
        } else {
            if (left + 1 <= n) {
                generateParenthesis(n, append + "(", left + 1, right, result);
            }
            if (left > right) {
                generateParenthesis(n, append + ")", left, right + 1, result);

            }
        }

    }

    public static ArrayList<String> generateParenthesis1(int n) {
        ArrayList<String> res = new ArrayList<>();
        generateCycle(n, 0, 0, "", res);
        return res;
    }

    private static void generateCycle(int n, int left, int right, String s, ArrayList<String> res) {
        if (right == n) {
            res.add(s);
            return;
        }

        if (left < n) {
            generateCycle(n, left + 1, right, s + "(", res);
        }

        if (left > right) {
            generateCycle(n, left, right + 1, s + ")", res);
        }
    }
}
